package com.gxc.tree;

import java.util.List;

/**
 * 派对的最大快乐值
 员工信息的定义如下:
 class Employee {
    public int happy;// 这名员工可以带来的快乐值
    List<Employee> subordinates;// 这名员工有哪些直接下级
 }
 公司的每个员工都符合 Employee 类的描述。
 整个公司的人员结构可以看作是一棵标准的、没有环的多叉树。
 树的头节点是公司唯一的老板。
 除老板之外的每个员工都有唯一的直接上级。
 叶节点是没有任何下属的基层员工(subordinates列表为空)，除基层员工外，每个员工都有一个或多个直接下级
 这个公司现在要办paty，你可以决定哪些员工来，哪些员工不来。但是要遵循如下规则。1.如果某个员工来了，那么这个员工的所有直接下级都不能来2.派对的整体快乐值是所有到场员工快乐值的累加3.你的目标是让派对的整体快乐值尽量大
 给定一棵多叉树的头节点boss，请返回派对的最大快乐值
 */
public class MaxHappiness {

    public class Employee {
        public int happy;// 这名员工可以带来的快乐值
        List<Employee> subordinates;// 这名员工有哪些直接下级
    }

    public class Info {
        public int bulaiHappy;
        public int laiHappy;

        public Info(int bulaiHappy, int laiHappy) {
            this.bulaiHappy = bulaiHappy;
            this.laiHappy = laiHappy;
        }
    }

    private Info maxHappy(Employee e) {
        if (e.subordinates.isEmpty()) {
            return new Info(0, e.happy);
        }
        //本人不去的快乐值,初始为0，加上下次的快乐值
        int bulai = 0;
        //本人去的快乐值
        int lai = e.happy;
        for (Employee employee : e.subordinates) {
            Info nextInfo = maxHappy(employee);
            lai += nextInfo.bulaiHappy;
            bulai += Math.max(nextInfo.bulaiHappy, nextInfo.laiHappy);
        }
        return new Info(bulai, lai);
    }

}
